package sort;

/*
    插入排序：
        把数组划分为 未排序 和 已排序 的两部分，每次从未排序部分中选一个插入到已排序数组的正确位置
        该开始时，第一个元素就是已排序的，然后我们逐步往右扩就可以了
 */
public class InsertSort {

    public static void main(String[] args) {
        Util.testFunction10000(InsertSort::insertSort);
    }

    public static int[] insertSort(int[] array) {
        int len = array.length;

        for (int i = 1; i < len; i++) {
            for (int j = i - 1; j >= 0; j--) {  // 从右往左走
                if (array[j] <= array[j+1]) {   // 左边是排好序的
                    break;
                }
                if (array[j] > array[j + 1]) {  // 如果前一个大于后一个，交换
                    Util.swap(array, j, j + 1);
                }
            }
        }

        return array;
    }
}
